package sf;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Trie {

    private static class TrieNode {
        private Map<Character, TrieNode> next = new ConcurrentHashMap<>();
        private volatile boolean isWord;
    }

    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode next = root;
        for (char c : word.trim().toCharArray()) {
            next.next.putIfAbsent(c, new TrieNode());
            next = next.next.get(c);
        }
        next.isWord = true;
    }

    public boolean search(String word) {
        TrieNode next = root;
        for (char c : word.trim().toCharArray()) {
            final TrieNode trieNode = next.next.get(c);
            if (trieNode == null) {
                return false;
            } else {
                next = trieNode;
            }
        }
        return next.isWord;
    }

    public boolean startWith(String word) {
        TrieNode next = root;
        for (char c : word.trim().toCharArray()) {
            final TrieNode trieNode = next.next.get(c);
            if (trieNode == null) {
                return false;
            } else {
                next = trieNode;
            }
        }
        return true;
    }




}
